|
Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems. They are modelled visually by square tiles with a color on each side. A set of such tiles is selected (for example the set in the picture). Then copies of the tiles are arranged side by side with matching colors, but ''without'' rotating or reflecting the tiles. The basic question about a set of Wang tiles is whether it can tile the plane or not, i.e., whether an entire infinite plane can be filled this way. The next question is whether this can be done in a periodic pattern. ==Domino problem== In 1961, Wang conjectured that if a finite set of Wang tiles can tile the plane, then there exists also a ''periodic'' tiling, i.e., a tiling that is invariant under translations by vectors in a 2-dimensional lattice, like a wallpaper pattern. He also observed that this conjecture would imply the existence of an algorithm to decide whether a given finite set of Wang tiles can tile the plane.〔. Wang proposes his tiles, and conjectures that there are no aperiodic sets.〕〔. Presents the domino problem for a popular audience.〕 The idea of constraining adjacent tiles to match each other occurs in the game of dominoes, so Wang tiles are also known as Wang dominoes.〔.〕 The algorithmic problem of determining whether a tile set can tile the plane became known as the domino problem.〔 According to Wang's student, Robert Berger,〔
In other words, the domino problem asks whether there is an effective procedure that correctly settles the problem for all given domino sets. In 1966, Wang's student Robert Berger solved the domino problem in the negative. He proved that no algorithm for the problem can exist, by showing how to translate any Turing machine into a set of Wang tiles that tiles the plane if and only if the Turing machine does not halt. The undecidability of the halting problem (the problem of testing whether a Turing machine eventually halts) then implies the undecidability of Wang's tiling problem.〔. Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Wang tile」の詳細全文を読む スポンサード リンク
|